/* C-based program to simulate a token-ring system
 * Service Discipline: Exhaustive service
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

double expon(double *, float);

#define NARS 20				//Number of arrivals per run at each station
#define SVTM 90				//Service time at each station
#define TPTM 1				//Token-passing time between stations

#define INF 100000000	//Indicate a very large number
#define NVALUE 10			//Number of different values of IATM
#define SVALUE 10			//Number of different values of NST
#define SMAX 19				//Maximum number of stations

#define IDEL 0
#define BUSY 1

double seed = 7654321;
double arrive[SMAX][NARS];	//arrival time of each packet at each station

//Time of arrival of all jobs at nst stations
void init(int nst, double iatm)
{
	int i,k;
	for (i = 0; i < nst; i ++) {
		arrive[i][0] = expon(&seed,iatm);
		for(k=1; k<NARS; k++)
		{
			arrive[i][k] = arrive[i][k-1] + expon(&seed,iatm);
		}
	}
}

int main(void)
{
	int NST;					//number of stations
	double IATM;				//Inter-arrival time at each station
	int n, dis, s, t, d, k;
	struct timeval time_start, time_stop;
    double time_pass;
    double clock;				//record current time
	double runtime[SVALUE];		//record the runtime for each NST value
	double sumwait;				//packets delay for each IATM value
	double wait[NVALUE];
	double totaltime;
	double cycletm[NVALUE];
	int passnum;				//token passing times between two stations
	int stnotdone;				//# stations not finish service
	int ifdone[SMAX]; 			// if station has finished all service
	int i[SMAX];				//current customer being served at each station
	int j[SMAX];				//next customer to arrive at each station
	double nextarrive[SMAX];	//next arrival time for each station
	double nextdepart[SMAX];	//next departure time for each station
	double queuelen[SMAX];		//queue length of each station
	
	//vary number of stations to get different run times
	for(n = 0; n < SVALUE; n ++)
	{
		runtime[n] = 0;
		NST = 10+n;
		//printf("NST = %f\r\n", NST);
		gettimeofday(&time_start, NULL);
		//vary inter-arrival time to get different loads
		for(dis = 0; dis < NVALUE; dis ++) {
			IATM = 100 + 50*dis;
			//printf("IATM = %f\r\n", IATM);
			clock = 0;
			stnotdone = NST;
			sumwait = 0;
			wait[dis] = 0;
			passnum = 0;
			totaltime = 0;
			cycletm[dis] = 0;
			init(NST, IATM);
			for(s = 0; s < NST; s++)
			{
				i[s] = 0;
				j[s] = 0;
				nextarrive[s] = arrive[s][0];
				nextdepart[s] = INF;
				queuelen[s] = 0;
				ifdone[s] = 0;
			}
			/* t is the station which currently holds the token	*/
			for(t = 0; t < NST; t = (t+1)%NST) {
				//printf("Token arrives at Station %d at %f\r\n", t, clock);
				if (ifdone[t] == 1) {
					//printf("Station %d done!\r\n", t);
					clock += TPTM;
					passnum ++;
					continue;
				}
				/* arrive all the packets up to now */
				while (nextarrive[t] < clock && j[t]<NARS) {
					//printf("clock = %f\r\n", clock);
					//sleep(1);
					//printf("1.Customer %d arrives at Station %d at %f\r\n", j[t], t, nextarrive[t]);
					queuelen[t] = queuelen[t] + 1.0;
					j[t] ++; 	//next customer to arrive
					if (j[t]<NARS)		//more type1 customers to arrive
						nextarrive[t] = arrive[t][j[t]];
					else
						nextarrive[t] = INF;
				}
				/* if there is someone in the queue	*/	
				while(queuelen[t] > 0) {
					//printf("Customer %d starts service at Station %d at %f\r\n", i[t], t, clock);
					queuelen[t] = queuelen[t] - 1.0;
					/* schedule next arrival and depart	*/
					nextdepart[t] = clock + expon(&seed,SVTM);
					/* keep handling arrival until depart happends	*/
					while(nextarrive[t] < nextdepart[t]) {
						//printf("2.Customer %d arrives at Station %d at %f\r\n", j[t], t, nextarrive[t]);
						clock = nextarrive[t];
						queuelen[t] = queuelen[t] + 1.0;
						j[t] ++;
						if (j[t]<NARS)		//more customers to arrive
							nextarrive[t] = arrive[t][j[t]];
						else
							nextarrive[t] = INF;
					}
					/* depart event handler	*/
					clock = nextdepart[t];
					//printf("Customer %d departs Station %d at %f\r\n", i[t], t, clock);
					sumwait += (clock - arrive[t][i[t]]);
					i[t] ++;
					if (i[t] < NARS) {
						clock += TPTM;
						passnum ++;
						continue;
					} else {
						ifdone[t] = 1;
						stnotdone --;
						//printf("stnotdone = %d\r\n", stnotdone);
						if (stnotdone == 0) {
							totaltime = clock;
							//printf("totaltime[%d] = %f\r\n", dis, totaltime);
							break;
						}
					}
				}
				if (stnotdone == 0) {
					break;
				}
				clock += TPTM;
				passnum ++;
				continue;
				//printf("stnotdone = %d\r\n", stnotdone);
				//printf("clock = %f\r\n", clock);
			}
			wait[dis] =sumwait / (NST*NARS);
			//printf("wait[%d] = %f\r\n", dis, wait[dis]);
			cycletm[dis] = totaltime / (passnum/NST);
			//printf("cycletm[%d] = %f\r\n", dis, cycletm[dis]);
		}
		gettimeofday(&time_stop, NULL);
		runtime[n] = ((double)time_stop.tv_sec -(double)time_start.tv_sec)*1000000 + (double)time_stop.tv_usec-(double)time_start.tv_usec;
		if (NST == 10) {
			printf("\r\n\r\n IATM vs. delays of packets (one '*' = 200)");
			for (d=0; d<NVALUE; d++){
				printf("\n  %d\t|", 100+50*d);
				//printf("wait[%d] = %f\r\n", d, wait[d]);
				//printf("sumwait[%d] = %f\r\n", d, sumwait[d]);
				for (k=0; k*200 < wait[d]; k++)
					printf("*");
			}
			printf("\r\n\r\n IATM vs. cycle-time of token (one '*' = 20)");
			for (d=0; d<NVALUE; d++){
				printf("\n  %d\t|", 100+50*d);
				//printf("cycletm[%d] = %f\r\n", d, cycletm[d]);
				for (k=0; k*20 < cycletm[NVALUE-d-1]; k++)
					printf("*");
			}
			printf("\r\n");
		}
	}
	printf("\r\n# stations vs. run time (one '*' = 0.1 msec)");
	for (d = 0; d < SVALUE; d++){
		printf("\nN=%5d |", 10+d);
		for (k=0; k*100 < runtime[d]; k++)
			printf("*");
	}
	printf("\r\n\r\n");
}
